// 2025/3/31
// https://leetcode.cn/problems/word-break/?envType=study-plan-v2&envId=top-100-liked
// 单词拆分

class Solution {
    public:
        bool wordBreak(string s, vector<string>& wordDict) {
            int n = s.size();
            unordered_set<string> wordDictSet(wordDict.begin(), wordDict.end());
            vector<bool> dp(n + 1, false);
            dp[0] = true;
            for(int i = 1; i <= n; i++)
            {
                for(int j = 0; j < i; j++)
                {
                    if(dp[j] && wordDictSet.count(s.substr(j, i - j)))
                    {
                        dp[i] = true;
                        break;
                    }
                }
            }
            return dp[n];
        }
    };

class Solution {
    public:
        bool wordBreak(string s, vector<string>& wordDict) {
            int n = s.size(), m = wordDict.size();
            vector<bool> dp(n + 1, false);
            dp[0] = true;
            for(int i = 0; i < n; i++)
            {
                if(!dp[i]) continue;
                for(int j = 0; j < m; j++)
                {
                    int len = wordDict[j].size();
                    string tmp = s.substr(i, len);
                    if(tmp == wordDict[j])
                    {
                        dp[i + len] = true;
                    }
                }
            }
            return dp[n];
        }
    };